package sort;

import java.util.Random;

/*
* 215. 数组中第k个最大元素
*
*       基于快速排序的选择排序, 也可使用堆排序
*
* */
public class FindKthLargest215 {
    Random random=new Random();
    public int findKthLargest(int[] nums, int k) {
       return quickSelect(nums,0,nums.length-1,nums.length-k);
    }

    private int quickSelect(int[] nums, int l, int r, int index) {
        int q=randomPartition(nums,l,r);
        if(q==index){
            return nums[q];
        }else{
            return q<index?quickSelect(nums,q+1,r,index):quickSelect(nums,l,q-1,index);
        }
    }

    private int randomPartition(int[] nums, int l, int r) {
        int i=random.nextInt(r-l+1)+l;
        swap(nums,i,r);
        return partition(nums,l,r);
    }

    private int partition(int[] nums, int l, int r) {
        int tmp=nums[r];
        int i=l-1;
        for(int j=l;j<r;j++){
            if(nums[j]<=tmp){
                swap(nums,++i,j);
            }
        }
        swap(nums,i+1,r);
        return i+1;
    }

    private void swap(int[] nums, int i, int r) {
        int tmp=nums[r];
        nums[r]=nums[i];
        nums[i]=tmp;
    }

}
